Nowadays, cryptography has an essential role in the communication of digital data so as to ensure a suitable level of security of the communication through the satisfying of requirements such as confidentiality and the privacy of the exchanged digital data.
The most frequently used cryptographic algorithms such as, for example, the Diffie-Hellmann algorithm, asymmetric key algorithms RSA and DSA (Digital Signature Algorithm), and ECC (Elliptic Curve Cryptosystem) often require the carrying out of modular mathematical operations on whole numbers consisting of thousands of bits.
Such modular mathematical operations comprise, for example, modular multiplications and computation operations of modular exponential functions.
Such mathematical operations can become vulnerable to different types of attacks developed by code crackers which continuously attempt, from an electronic and/or information point of view, to violate the already-existing cryptographic algorithms, in particular those with asymmetric keys. Among the most recent and dangerous types of attack, SCA (Side-Channel Attacks) can jeopardize the security of secret keys used in encrypting/decrypting operations.
In particular, a Side-Channel Attack SCA is an attack by which the recovery of secret information (in particular, the secret key) is obtained by a code cracker without exploiting particular weaknesses in the corresponding mathematical theory, but rather by exploiting problems related to the physical implementation of the cryptographic algorithm itself. For example, a Side-Channel Attack can consist, by the code cracker, of monitoring timing information, or of measuring power consumption or electromagnetic emissions during the encrypting/decrypting operations. Moreover, such an attack can consist of injecting a fault (e.g., overvoltage or glitch, also undervoltage) in the electronic device configured so as to implement a cryptographic algorithm, for example, through a laser or by altering a supply voltage. From the comparison between the encrypted message obtained by the electronic device in the case in which there is an injected fault and the encrypted message obtained by the electronic device in the case of normal operation (without perturbations by the code cracker) or by monitoring power consumption, a code cracker may be capable of obtaining fundamental information for successfully recovering the secret key used by electronic devices under attack.
A Side-Channel Attack of the known type is Differential Power Analysis (DPA), which is based upon a measurement of power consumption of an electronic device arranged for carrying out encrypting/decrypting operations.
For example, the DPA attack can be aimed against cryptographic algorithms which foresee modular computation operations of exponential functions, as occurs, for example, in algorithms with asymmetric keys RSA and DSA. For example, with reference to the RSA algorithm, an encrypted message c is obtained from an uncoded message m through the computation of a modular exponential function in a mathematical ring of the integer numbers n module n (in which n is the product of two prime numbers) expressed by the following relationship:c=me mod n  (1)in which:e is a public exponent of the algorithm RSA, in particular it is a part of the public key used by such an algorithm;
mod n represents an operation of modular reduction relative to the aforementioned mathematical ring n. It should be observed that the module n is part of the public key relative to the algorithm RSA.
Similarly, the un-encoded message m can be obtained again by decrypting the encrypted message c through the computation of a further exponential function of the modular type expressed from the following relationship:m=cd mod n  (2)in which d represents the secret key used by the RSA algorithm.
It should be observed that the modular computation operations of exponential functions (1) and (2) mentioned above are calculated, generally, by carrying out a multitude of modular multiplications through a conventional Square and Multiply Algorithm.
As it is known, an electronic device that carries out modular multiplications corresponding to the computation of one of such exponential functions, for example the function (2) relative to the operation of decrypting a message c with secret key d, consumes some power. In a DPA attack, such a power consumption can be measured with an oscilloscope and can be represented in the form of a multitude of power traces.
In addition, for each modular multiplication suitable for approximating the relationship (2), the code cracker is capable of knowing both an item of input data to such an operation, and a result from the multiplication generated as a function of a bit of the secret key d. Therefore, on the basis of a forecast of the result generated by each modular multiplication and on the basis of a processing of measured power traces, the DPA method may allow the code cracker to reconstruct each bit of the secret key d of the algorithm RSA.
Some methods have recently been developed to counter the DPA Side-Channel Attack, with reference, in particular, to a decrypting operation of an encrypted message c. Each of such methods, which are conventional and which are commonly known as blinding methods or techniques, foresees the introduction in the decrypting operation (2) of a secret parameter, for example, a number generated in a random manner rand. Indeed, the introduction of such a random number rand makes the DPA attack very difficult or substantially impossible since the computation of the exponential decrypting function (2) is carried out on an item of data which has been suitably blinded from the random number, and, therefore, which has become, in such a way, unknown to the code cracker.
Such known blinding methods shall be described, for example, with reference to the decrypting operation (2) of an encrypted message c relative to the RSA algorithm. Analogous considerations can also be applied to the DSA algorithm and to other algorithms with a public key.
A first known blinding method foresees the introduction of the aforementioned random number rand in the message c to be decrypted. An intermediate result C1 of the decrypting operation can, therefore, be expressed as:C1=(c*rande)d mod n  (3)which, based on the relationship (1), is equal to:C1=(me*rande)d(mod n)=m*rand(mod n)  (4)since (rande)d=rand mod n and (me)d=m(mod n).
In order to obtain the un-encoded message m again, the intermediate result C1 is further multiplied by the inverse of the random number rand.
Such a first blinding method has the drawback of requiring the computation of the modular inverse of the random number rand so as to restore the original un-encoded message m. Indeed, as it is known, the inversion operation is an expensive operation in terms of computational time required. Moreover, such a first method requires the computation of the additional exponential function rande.
A second known blinding method foresees the introduction of the aforementioned random number rand in the modular reduction operation. In particular, the module n is multiplied by the aforementioned random number rand so as to obtain:n′=rand*n  (5)
In such a case, a respective intermediate result C2 of the decrypting operation can be calculated through the following relationship:C2=cd mod n′  (6)
Such an intermediate result C2 must still undergo an operation of modular reduction for n so as to restore the original un-encoded message m:m=C2 mod n=cd mod n=m  (7)
In other words, such a second method has the drawback of requiring the computation of an additional modular reduction operation. Moreover, such a second method is not very versatile since it imposes restrictions on the random number rand, which cannot be zero, so as to prevent the whole operation from returning to zero.
A third known blinding method foresees the introduction of the random number rand in the private key d used to decipher the encrypted message c. In particular, from the aforementioned random number rand, a new private key d′ can be calculated based on the relationship:d′=d+rand*phi(n)  (8)
i.e., adding to the private key d a random multiple of phi(n), where phi(n) is the known Euler function.
With reference to the aforementioned decryption operation (2), the un-encoded message m can be obtained based upon the following relationship:cd′(mod n)=cd+rand*phi(n)(mod n)=cd*crand*phi(n)(mod n)==cd*1(mod n)=cd(mod n)=m  (9)since Euler's theorem is validck*phi(n)mod n=1 for each c, k and n.  (10)
It should be observed that such a third method has the drawback of requiring an increase in the exponent in function of the size of the random number rand. In such a way, for every additional bit of the exponent, it is necessary to carry out many modular multiplications. Moreover, such a method requires the storage of the Euler function phi(n) in a memory of the electronic device that implements the method.